递归和动态规划——换钱最少的货币数（面值不重复，一张可重复使用）

Posted on | In ,

题目：给定一个数组arr，arr中的值不重复，每个值代表一种货币，但每种可以重复使用。给定一个整数aim，求组成aim值的最少货币数。

实现：如果arr的长度为N，则生成行数为N*（aim+1）的动态规划矩阵dp。时间复杂度和额外的空间复杂度都为O（N*aim）。dp[i][j]的含义是，在任意使用货币arr[0,..i]的情况下，组成货币j的最小张数。

  1. 如果arr为空，或长度为0，或aim<1，不需要任何货币，返回0。
  2. 对于N*（aim+1）的dp矩阵，
    1）dp[0][0,..aim+1]表示只能用货币arr[0]来找aim值的最小货币数。可以看出，只有当aim为arr[0]的倍数时，才找得开，这些位置为1,2,3，…。而其他不是倍数的地方，aim是找不开的，即不存在最小货币数，无解，我们设为max=Intefer.MAX_VALUE，表示32位整数的最大值，即2^31-1=2147483647。
    2）dp[0,..N][0]表示aim为0需要的最小货币数，即不需要找，应该全为0。
    3）对于i>0，j>0的行，我们从左往右，从上到下进行计算。对于位置(i，j），最小货币数dp[i][j]的值可能来自以下几种情况之一：
    （1）完全不使用当前货币arr[i]，只使用arr[0,…i-1]货币的情况下的最少张数，即dp[i-1][j]的值；
    （2）使用1张当前货币arr[i]情况下的最少张数，即dp[i-1][j-arr[i]]+1;（考虑dp[i-1][j-arr[i]]，返回到上次未使用arr[i]的地方，即第i-1行，这个值代表可以任意使用arr[0,..i-1]情况下，组成钱数j-arr[i]所需的最小张数。从钱数为j-arr[i]到钱数为j，只需要加上当前货币arr[i]。所以dp[i][j]可能等于dp[i-1][j-arr[i]]+1。）
    （3）使用2张当前货币arr[i]情况下的最少张数，即dp[i-1][j-2*arr[i]]+2;
    以此类推，在所有情况中，取张数最小的，即
    dp[i][j]=min{dp[i-1][j-k*arr[i]] + k},其中0<=k
    化简上面这个式子:
    dp[i][j]=min{dp[i-1][j],min{dp[i-1][j-k*arr[i]]+k}},其中k>=1
    dp[i][j]=min{dp[i-1][j],min{dp[i-1][j-(y+1)*arr[i]]+(y+1)}}
    =min{dp[i-1][j],min{dp[i-1][j-y*arr[i]-arr[i]]+y+1}},其中y>=0
    又因dp[i-1][j-yarr[i]]+y=dp[i][j]，（考虑dp[i-1][j-y\arr[i]](返回到上次未使用y*arr[i]的地方，即第[i-1]行），这个值代表可以任意使用arr[0,..i-1]情况下，组成钱数j-y*arr[i]所需的最小张数。从钱数为j-y*arr[i]到钱数为j，只需要加上k张当前货币y*arr[i]。所以dp[i][j]可能等于dp[i-1][j-y*arr[i]]。）
    min{dp[i-1][j-arr[i]-y*arr[i]]+y}=dp[i][j-arr[i]],其中y>=0
    最终得到:
    dp[i][j]=min{dp[i-1][j],dp[i][j-arr[i]]+1}.
    如果j-arr[i]<0表示arr[i]太大，用一张都会超过aim=j的值，令dp[i][j]=dp[i-1][j]即可。
    4）若最终不存在最少货币数，返回-1；存在的话，则返回最小货币数。（注意计算过程中是用max表示不存在，而最终为了好看，不存在用-1表示）

例子：
arr=[5,2,3,1],aim=5

dp矩阵 0 1 2 3 4 5
5 0 max max max max 1
2 0 max 1 max 2 1
3 0 max 1 1 2 1
1 0 1 1 1 2 1

注意0-1背包问题：一个背包aim，装3种物品，每种物品的重量wi，物品价值pi,求怎样使背包的价值最大。
dp[i][j]=max{dp[i-1][j],dp[i-1][j-arr[i]]+pi}

动态规划进阶：利用长度为aim+1的数组滚动更新。由于dp[i][j]=min{dp[i-1][j],dp[i][j-arr[i]]+1}，可以看出按行更新只需要1个一维数组，而按列更新需要的以为数组个数与arr中货币最大值有关，如货币最大值为a，则表示数组最差要往左跳a下，就要准备a个以为数组不断滚动，这样比较麻烦，因此按行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * 求解得到aim的最小货币数
 */
public class MinCoins {
	/**
	 * 求解得到aim的最小货币数（arr中的值不重复，每个值代表一种货币，但每种可以重复使用）
	 * @param arr 输入的货币值数组，每个值都不相等
	 * @param aim 需要求解的货币总数
	 * @return 刚好生成需要求解的货币总数的最小货币数
	 */
	public int minCoins1(int[] arr, int aim) {
		if (arr == null || arr.length < 0 || aim < 0) {
			return -1; //表示不存在最小货币数满足aim要求
		}
		int m = arr.length; //矩阵的行
		int n = aim + 1; //矩阵的列
		int max = Integer.MAX_VALUE; //不存在最小货币数满足要求，则dp[i][j]=max
		int[][] dp = new int[m][n];
		//对第一行特殊处理，它只能使用arr[0]
		//dp[0][0] = 0;
		for (int j = 1; j < n; j++) {
			dp[0][j] = max;  //先让所有为max，后面的if再将符合条件的修改
			//如果dp[0][j]前面的dp[0][j-arr[0]]不为max，说明此时又到了arr[0]倍数的地方
			if (j >= arr[0] && dp[0][j-arr[0]] != max) { 
				dp[0][j] = dp[0][j - arr[0]] + 1;
			}
		}
		/*for (int i = 1; i < m; i++) {
			dp[i][0]=0;
		}*/
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) { 
				//下面这步求解左边的
				int left = max;
				if (j >= arr[i] && dp[i][j-arr[i]] != max) {
					left = dp[i][j-arr[i]] + 1;
				}
				//将左边的与上边的比较大小
				dp[i][j] = Math.min(left, dp[i-1][j]);
			}
		}
		return dp[m-1][aim] != max ? dp[m-1][aim] : -1; //若最终不存在最少货币数，返回-1；存在的话，则返回最小货币数。
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
   /**
 * 利用空间压缩进行更新，设长度为aim+1的数组（以列更新）
 * @param arr
 * @param aim
 * @return
 */
public int minCoins2(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return -1;
	}
	int m = arr.length;
	int max = Integer.MAX_VALUE; //无解时用max表示，表示没有最小货币数
	int n = aim + 1;
	int[] dp = new int[n]; //滚动更新的数组
	//dp[0] = 0;
	for (int j = 1; j < n; j++) {
		dp[j] = max;
		if(j >= arr[0] && dp[j - arr[0]] != max) {  //初始化数组，相当于对dp矩阵的第一行赋值
			dp[j] = dp[j - arr[0]] + 1;
		}
	}
	for (int i = 1; i < m; i++) { //下面需要进行滚动更新的次数
		for (int j = 1; j < n; j++) { //每一行的更新
			int left = max;
			if (j >= arr[i] && dp[j-arr[i]] != max) {
				left = dp[j - arr[i]] + 1;
			}
			dp[j] = Math.min(left, dp[j]);
		}
	}
	return dp[n-1] != max ? dp[n - 1] : -1;
}
1
2
3
4
5
6
7
8
9
	//Test
	public static void main(String[] args) {
		MinCoins minC = new MinCoins();
		int[] arr = {5, 3, 2};
		int aim = 10;
		System.out.println(minC.minCoins1(arr, aim));
		System.out.println(minC.minCoins2(arr, aim));
	}
}